//The demons had captured the princess and imprisoned her in the bottom-right co
//rner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Ou
//r valiant knight was initially positioned in the top-left room and must fight hi
//s way through dungeon to rescue the princess. 
//
// The knight has an initial health point represented by a positive integer. If 
//at any point his health point drops to 0 or below, he dies immediately. 
//
// Some of the rooms are guarded by demons (represented by negative integers), s
//o the knight loses health upon entering these rooms; other rooms are either empt
//y (represented as 0) or contain magic orbs that increase the knight's health (re
//presented by positive integers). 
//
// To reach the princess as quickly as possible, the knight decides to move only
// rightward or downward in each step. 
//
// Return the knight's minimum initial health so that he can rescue the princess
//. 
//
// Note that any room can contain threats or power-ups, even the first room the 
//knight enters and the bottom-right room where the princess is imprisoned. 
//
// 
// Example 1: 
//
// 
//Input: dungeon = [[-2,-3,3],
//              [-5,-10,1],
//              [10,30,-5]]
//Output: 7
//Explanation: The initial health of the knight must be at least 7 if he follows
// the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.
// 
//
// Example 2: 
//
// 
//Input: dungeon = [[0]]
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// m == dungeon.length 
// n == dungeon[i].length 
// 1 <= m, n <= 200 
// -1000 <= dungeon[i][j] <= 1000 
// 
// Related Topics 数组 动态规划 矩阵 
// 👍 478 👎 0


package leetcode.editor.cn;

import java.util.Arrays;

//Java：Dungeon Game
class P174DungeonGame {
    public static void main(String[] args) {
        Solution solution = new P174DungeonGame().new Solution();
        // TO TEST
        solution.calculateMinimumHP(new int[][]{{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int calculateMinimumHPMy(int[][] dungeon) {
            int[][] memo = new int[dungeon.length][dungeon[0].length];
            for (int i = 0; i < memo.length; i++) {
                if (i == 0) {
                    memo[i][0] = dungeon[i][0];
                } else {
                    memo[i][0] += dungeon[i][0] + memo[i - 1][0];
                }
            }
            for (int i = 0; i < memo[0].length; i++) {
                if (i == 0) {
                    memo[0][i] = dungeon[0][i];
                } else {
                    memo[0][i] += dungeon[0][i] + memo[0][i - 1];
                }
            }
            for (int i = 1; i < dungeon.length; i++) {
                for (int j = 1; j < dungeon[0].length; j++) {
                    int k = memo[i][j];
                    memo[i][j] = Math.min(memo[i - 1][j] + k, memo[i][j - 1] + k);
            }
            }

            return -memo[dungeon.length - 1][dungeon[0].length - 1];
        }
        public int calculateMinimumHP(int[][] dungeon) {
            int n = dungeon.length, m = dungeon[0].length;
            int[][] dp = new int[n + 1][m + 1];
            for (int i = 0; i <= n; ++i) {
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }
            dp[n][m - 1] = dp[n - 1][m] = 1;
            for (int i = n - 1; i >= 0; --i) {
                for (int j = m - 1; j >= 0; --j) {
                    int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
                    dp[i][j] = Math.max(minn - dungeon[i][j], 1);
                }
            }
            return dp[0][0];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}